1. Technical Field
The invention relates to a computer graphics system for processing and displaying graphical data representing three-dimensional objects, and, more particularly, to the rasterization of the objects for display.
2. Description of the Prior Art
Computer graphics systems are frequently used to model a scene having three-dimensional objects and display the scene on a two-dimensional display device such as a cathode ray tube or liquid crystal display. Typically, the three-dimensional objects of the scene are each represented by a multitude of polygons (or primitives) that approximate the shape of the object. Rendering the scene for display on the two-dimensional display device is a computationally intensive process. It is therefore frequently a slow process, even with today's microprocessors and graphics processing devices.
Rasterization is the process which converts the simple, geometric description of a graphics primitive into pixels for display. A typical primitive, as shown in FIG. 1A, is a triangle T.sub.1. Other area or surface primitives conventionally are converted into one or more triangles prior to rasterization. Consequently, the conventional rasterization process need only to handle triangles. The triangle T.sub.1 is represented by the (x,y,z) coordinates and other properties (such as colors and texture coordinates) at each of its vertices. The (x,y) coordinates of a vertex tell its location in the plane of the display. The z coordinate tells how far the vertex is from the selected view point of the three-dimensional scene. Rasterization may be divided into three tasks: scan conversion, shading, and visibility determination.
Scan conversion utilizes the (x,y) coordinates of the vertices of each triangle to compute a set of pixels S which cover the triangle.
Shading computes the colors of each pixel in the set S. There are numerous schemes for computing colors, some of which involve computationally intensive techniques such as texture mapping.
Visibility determination utilizes the z coordinate, also called the depth value, of each pixel to compute the set of pixels S.sub.v (a subset of S) which are "visible" for the triangle. The z coordinate of each pixel may be determined by interpolation between the z coordinate specified for each vertex of the triangle. The set S.sub.v will differ from the set S if any of the pixels in set S cover the previously rasterized triangles whose z values are closer to the selected view point. Thus, for each triangle in the scene, a pixel is "visible" if it is in the set S.sub.v or "hidden" if it is the set S but not in the set S.sub.v. Moreover, a triangle is "all visible" if the set S.sub.v is identical to set S, "partially hidden" if the set S.sub.v is not identical to set S and set S.sub.v is not empty, or "all hidden" if set S.sub.v is empty. For example, FIG. 1B shows two triangles, T1 and T2, wherein triangle T1 is partially hidden by triangle T2.
Moreover, the rasterization process may include lighting calculations that simulate the effects of light sources upon the surfaces of the triangles of the scene. Typically, the position of each triangle is identified by (x,y,z) coordinates of a set of three vertices, with each vertex having a reflectance normal vector with the vertex at its origin. The reflectance normal vectors of each triangle along with information about the position of the light sources are used to calculate the effect of the light sources on the color values determined during the shading calculations for each triangle.
Rasterization is completed by writing the colors of the set of visible pixels S.sub.v to an image buffer for display, and writing the z coordinate of the set of visible pixels S.sub.v to a Z-buffer.
Rasterization is typically the bottleneck in the rendering process. Therefore, the efficiency of the rasterization process and, in particular, the shading operation is extremely important. Typically, the shading operation calculates the color of each pixel in the set S, whether or not the pixel is in fact "visible". Then, during visibility testing, if the pixel is found to be visible, the color of the pixel is written to the image buffer. For triangles which are entirely hidden, the shading calculations are wasted at every pixel, which decreases the efficiency of the rasterization process.
Thus, there is a need for a computer graphics system that is more computationally efficient and that reduces the number of unnecessary shading calculations during the rendering process.